package 力扣._146_LRU缓存;

import java.util.HashMap;
import java.util.Map;

class LRUCache2 {
    // 使用双向链表记录访问顺序，将最近访问的节点移到表头，节点包含（value、）
    // HashMap用于实现快速找到key对应的链表节点，Map节点应为（key, 链表节点）
    class DLinkList {
        int key;
        int value;
        DLinkList front;
        DLinkList next;

        public DLinkList(int key, int value, DLinkList front, DLinkList next) {
            this.key = key;
            this.value = value;
            this.front = front;
            this.next = next;
        }
    }

    Map<Integer, DLinkList> map;
    DLinkList head; // 头结点
    DLinkList tail; // 尾结点

    int capacity = 0;

    public LRUCache2(int capacity) {
        map = new HashMap<>(capacity);

        head = new DLinkList(-1, -1, null, null);
        tail = new DLinkList(-1, -1, head, null);
        head.next = tail;
        this.capacity = capacity;
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            DLinkList node = map.get(key);
            // 先断两边
            node.front.next = node.next;
            node.next.front = node.front;
            // 再移到表头
            node.next = head.next;
            head.next.front = node;
            head.next = node;
            node.front = head;

            return node.value;

        } else {
            return -1;
        }
    }

    public void put(int key, int value) {
        // 如果已存在
        if (map.containsKey(key)) {
            DLinkList node = map.get(key);
            node.value = value;

            // 先断两边
            node.front.next = node.next;
            node.next.front = node.front;
            // 再移到表头
            node.next = head.next;
            head.next.front = node;
            head.next = node;
            node.front = head;

            return;
        }
        // 不存在
        // 若容量已满，则删除表尾结点
        if (map.size() == capacity) {
            DLinkList last = tail.front;
            map.remove(last.key);
            last.front.next = tail;
            tail.front = last.front;
        }
        DLinkList node = new DLinkList(key, value, head, head.next);
        head.next.front = node;
        head.next = node;

        map.put(key, node);
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */